package com.sheng.leetcode.year2022.month06.day23;

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author liusheng
 * @date 2022/06/23
 *
 * 30. 串联所有单词的子串
 *
 * 给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
 * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。
 *
 * 示例 1：
 * 输入：s = "barfoothefoobarman", words = ["foo","bar"]
 * 输出：[0,9]
 * 解释：
 * 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
 * 输出的顺序不重要, [9,0] 也是有效答案。
 *
 * 示例 2：
 * 输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
 * 输出：[]
 *
 * 示例 3：
 * 输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
 * 输出：[6,9,12]
 *
 * 提示：
 *
 * 1 <= s.length <= 104
 * s 由小写英文字母组成
 * 1 <= words.length <= 5000
 * 1 <= words[i].length <= 30
 * words[i] 由小写英文字母组成
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/substring-with-concatenation-of-all-words
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0030 {

    @Test
    public void test01(){
//        String s = "barfoothefoobarman";
//        String[] words = {"foo","bar"};//0, 9
//        String s = "wordgoodgoodgoodbestword";
//        String[] words = {"word","good","best","word"};//
//        String s = "barfoofoobarthefoobarman";
//        String[] words = {"bar","foo","the"};//6, 9, 12
//        String s = "wordgoodgoodgoodbestword";
//        String[] words = {"word","good","best","good"};//8
        String s = "ababaab";
        String[] words = {"ab","ba","ba"};//1
        List<Integer> list = new Solution().findSubstring(s, words);
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }

}
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        //key为words数组中的单词，value为单词出现的次数
        Map<String, Integer> keyMap = new HashMap<>(16);
        for (String word : words) {
            keyMap.put(word, keyMap.getOrDefault(word, 0) + 1);
        }
        List<Integer> list = new ArrayList<>();
        //将数组中的单词去重，防止重复计算
        Set<String> set = Arrays.stream(words).collect(Collectors.toSet());
        //串联起来之后的长度
        int wordsLength = words.length;
        int wordLength = words[0].length();
        int length = wordsLength * wordLength;
        //遍历字符串内符合长度的所有子串
        for (int i = 0; i <= s.length() - length; i++) {
            //该字符串内所有的单词出现的次数
            Map<String, Integer> map = new HashMap<>(16);
            String substring = s.substring(i, i + length);
            //index用于计算，已经存放到map中的单词的数量，必须小余单词数组的数量
            int index = 0;
            //循环判断当前子串中每个单词出现的次数，并存在map中
            while (index < wordsLength) {
                //防止ababa出现计算了两次ab，两次ba的情况
                //将子串以wordLength长度进行分割
                String sub = substring.substring(index * wordLength, (index + 1) * wordLength);
                //判断分割出来的单词是否存在于keyMap中
                if (keyMap.containsKey(sub)) {
                    int value = map.getOrDefault(sub, 0);
                    map.put(sub, value + 1);
                    //判断当前单词的value和keyMap中该单词的value大小
                    if (map.get(sub) > map.get(sub)) {
                        break;
                    }
                } else {
                    break;
                }
                index++;
            }
            //判断子串中各个单词出现的次数是否和原数组中各个单词出现的次数保持一致
            boolean flag = true;
            for (String word : set) {
                if (!keyMap.get(word).equals(map.get(word))) {
                    flag = false;
                }
            }
            //一致，则代表当前子串是单词的串联
            if (flag) {
                list.add(i);
            }
        }
        return list;
    }
}
